package leetcode.greedy;


/**
 * 
 * @author 26233
 *
 *给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

 

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
 

说明：

1 <= n <= 10 ^ 4
- 10 ^ 5 <= nums[i] <= 10 ^ 5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/non-decreasing-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode665_NonDecreasingArray {
	
	/**
	 * 
	 * @param nums
	 * @return
	 * 
	 * 在不满足条件的元素位置考虑前后元素和本身的值的修改情况
	 * 在遍历到当前位置时，当前位置之前的数据已经满足条件了，因此只需要考虑修改当前元素或者后一个元素
	 */
	
	public static boolean checkPossibility(int[] nums) {

		int changeTimes = 0;
		for(int i = 0; i <= nums.length - 2; i++) {
			if(i == 0) {
				// [4, -1, 2, 3]
				if(nums[i + 1] < nums[i]) {
					nums[i] = nums[i + 1];
					changeTimes++;
				}
			}else {
				// 非递增时-1，考虑如何修改能导致最少的修改
				if(nums[i] > nums[i + 1]) {
					// 如果后一个元素大于前一个元素，[-1, 4, 3]
					if(nums[i + 1] > nums[i - 1]) {
						nums[i] = nums[i - 1];
					// 如果后一个元素等于前一个元素, [-1, 4, -1]
					}else if(nums[i + 1] == nums[i - 1]) {
						nums[i] = nums[i + 1];
					// 如果后一个元素小于前一个元素，考虑前面的元素都已满足条件，将后一元素设置为当前值，[2, 4, 1, 5],[5, 7, 1, 8]
					}else {
						nums[i + 1] = nums[i];
					}
					changeTimes++;
				// 非递增时-2， 当前元素小于前一元素，且不大于后一元素，[3, 2, 3]
				}else if(nums[i] < nums[i - 1]) {
					nums[i] = nums[i - 1];
					changeTimes++;
				}
			}
		}
		// 检查最后没有判断到的元素
		if(nums.length > 1 && nums[nums.length - 1] < nums[nums.length - 2])
			changeTimes++;
		
		return changeTimes < 2;
    }
	
	public static void main(String[] args) {
		int[] input = {1, 4, 1, 2};
		checkPossibility(input);
	}

}
